import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Stream;

/**
 * @author yu
 * @date 2025年06月02日 22:59
 * @description 39. 组合总和
 *
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
 * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
 * 并以列表形式返回。    你可以按 任意顺序 返回这些组合。
 *
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * 示例 1：
 *  输入：candidates = [2,3,6,7], target = 7
 *  输出：[[2,2,3],[7]]
 *
 */
public class _07_backtracking_05_39 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, path, candidates, target, 0, 0);
        return res;
    }

    public static void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        try {
            // 读取 candidates 数组
            /*String[] input = scanner.nextLine().trim().split("\\s+");
            int[] candidates = Stream.of(input)
                    .mapToInt(Integer::parseInt)
                    .toArray();
            */
            String[] input = scanner.nextLine().split(" ");
            int[] candidates = new int[input.length];
            for (int i = 0; i < input.length; i++) {
                candidates[i] = Integer.parseInt(input[i].trim());
            }

            int target = scanner.nextInt();

            // 计算结果
            List<List<Integer>> result = combinationSum(candidates, target);

            System.out.println(result);

        } catch (Exception e) {
            System.out.println("输入格式错误，请输入整数数组和目标值");
        } finally {
            scanner.close();
        }
    }
}
